package Tree_;

/*
 *@Student 张策
 */
public class BinaryTree {
     public static class TreeNode{
            char val;
            TreeNode left;
            TreeNode right;
        public TreeNode(char val) {
            this.val = val;
        }
    }
    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }
    public TreeNode find(TreeNode root ,int val){
         if (root==null){
             return null;
         }
         if(root.val==val){
             return root;
         }
        TreeNode tr1 = find(root.left, val);
        TreeNode tr2 = find(root.right, val);
        if(tr1!=null){
            return tr1;
        }
        if(tr2!=null){
            return tr2;
        }
             return null;
    }
    public boolean isSameTree(TreeNode p, TreeNode q) {
         //结构不同
         if(p!=null&&q==null||p==null&&q!=null){
             return false;
         }
         //都为空返回
         if(p==null&&q==null){
             return true;
         }
         if(p.val!=q.val){
             return false;
         }
         return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
         if(root==null){
             return true;
         }
         if(isSameTree(root,subRoot)){
             return true;
         }
         if(isSubtree(root.left,subRoot)){
             return true;
         }
         if (isSubtree(root.right,subRoot)){
             return true;
         }
         return false;
    }
    //对称
    public boolean isSymmetric(TreeNode root) {
         if (root==null){
             return true;
         }
         return isSymmetricChild(root.left,root.right);
    }
    public boolean isSymmetricChild(TreeNode rootleft,TreeNode rootright) {
         if(rootleft==null&&rootright==null){
             return true;
         }
         if (rootleft==null&&rootright!=null||rootleft!=null&&rootright==null){
             return false;
         }
         if(rootleft.val!=rootright.val){
             return false;
         }
       return   isSymmetricChild (rootleft.left,rootright.right)&&
         isSymmetricChild (rootleft.right,rootright.left);
    }
}
